package 剑指offer;

import java.util.ArrayList;
import java.util.Scanner;

/** 

* @author ：soulstones
* @version ：2019年9月30日 下午9:57:41 
* @Description：
* 
输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
输出描述:
对应每个测试案例，输出两个数，小的先输出。
*/
public class A42和为S的两个数字 {

	//因为数组是递增序列，所以可以考虑在头，尾两个指针进行移动，类似于滑动窗口
	
	//好吧。这是找出所有两个数和为sum的组合（前提是数组有序，递增的）
	 public static ArrayList<ArrayList<Integer>> FindNumbersWithSum(int [] array,int sum) {
		ArrayList<ArrayList<Integer>> result = new ArrayList<>();
		int low = 0;
		int high = array.length - 1;
		while (low < high) {
			int cur = array[low] + array[high];
			ArrayList<Integer> list = new ArrayList<>();
			if (cur == sum) {
				list.add(array[low]);
				list.add(array[high]);
				result.add(list);
				low++;
				high--;
			} else if (cur < sum) {
				low++;
			} else {
				high--;
			}
		}
		return (ArrayList<ArrayList<Integer>>) result;
	}
	 
//因为是递增数组，最小的数字加上一个数和为S，那么这两个数的乘积也是最小的；循环遍历外层，里层用二分法。
	public static ArrayList<Integer> FindNumbersWithSum11(int[] array, int sum) {
		ArrayList<Integer> p = new ArrayList<Integer>();
		for (int i = 0; i < array.length; i++) {
			int low = i + 1;
			int hight = array.length;
			int mid;
			Boolean f = false;
			while (low < hight) {
				mid = (low + hight) / 2;
				if (array[i] + array[mid] == sum) {
					p.add(array[i]);
					p.add(array[mid]);
					f = true;
					break;
				} else if (array[i] + array[mid] > sum) {
					hight = mid - 1;
				} else {
					low = mid + 1;
				}
			}
			if (f == true) {
				break;
			}
		}
		return p;
	}
	 
	 public static void main(String[] args) {
		 Scanner scanner = new Scanner(System.in);
			String s = scanner.nextLine();
			String[] ss = s.split(" ");
			int [] arr=new int [ss.length];
			for (int i = 0; i < arr.length; i++) {
				arr[i]=Integer.parseInt(ss[i]);
			}
			int sum = scanner.nextInt();
			System.out.println(FindNumbersWithSum(arr, sum));
			
			System.out.println(FindNumbersWithSum11(arr, sum));
	}
}
